package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/remove-methods-from-project/description/
 * @create 2025/9/18 22:07
 * @since JDK17
 */

public class Solution07 {
    boolean[] vis;
    int n;
    List<Integer> ans = new ArrayList<>();
    List<List<Integer>> g = new ArrayList<>();
    void dfs(int cur) { // 收集所有的可疑方法
        vis[cur] = true;
        for (int x : g.get(cur)) {
            if (!vis[x]) {
                dfs(x);
            }
        }
    }

    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        vis = new boolean[n];
        this.n = n;
        int m = invocations.length;
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
            ans.add(i);
        }
        for (int i = 0; i < m; i++) {
            int from = invocations[i][0], to = invocations[i][1];
            g.get(from).add(to);
        }
        dfs(k);
        for (int i = 0; i < m; i++) {
            int from = invocations[i][0], to = invocations[i][1];
            if (!vis[from] && vis[to]) {  // 可疑方法之外的方法调用了
                return ans;
            }
        }
        ans.clear();
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ans.add(i);
            }
        }
        return ans;
    }
}
